package com.xj.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 杨辉三角
 */
public class L118_杨辉三角 {

    /**
     *给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
     *
     * 在杨辉三角中，每个数是它左上方和右上方的数的和。
     *
     * 示例:
     *
     * 输入: 5
     * 输出:
     * [
     *      [1],
     *     [1,1],
     *    [1,2,1],
     *   [1,3,3,1],
     *  [1,4,6,4,1]
     * ]
     */
    public static void main(String[] args) {
        System.out.println(generateOffice(5));
        System.out.println(generateOffice(0));
        System.out.println(generateOffice(1));
        System.out.println(generateOffice(2));
        System.out.println(generateOffice(3));
    }

    //自己的解法：二维数组
    public static List<List<Integer>> generate(int numRows) {
        int[][] arr=new int[numRows][numRows];
        if(numRows==0){
            return  new ArrayList<>();
        }else if(numRows==1){
            arr[0][0]=1;
        }else if(numRows==2){
            arr[0][0]=1;
            arr[1][0]=1;
            arr[1][1]=1;
        }else {
            arr[0][0]=1;
            arr[1][0]=1;
            arr[1][1]=1;
            for (int i = 2; i < numRows; i++) {
                arr[i][0] = 1;
                arr[i][i] = 1;
                for (int j = 1; j < i; j++) {
                    int a = arr[i - 1][j - 1];
                    int b = arr[i - 1][j];
                    arr[i][j] = a + b;
                }
            }
        }

        List<List<Integer>> result=new ArrayList<>();
        int row=arr.length;
        for (int i=0;i<row;i++){
            List<Integer> list=new ArrayList<>();
            for(int j=0;j<=i;j++){
                list.add(arr[i][j]);
            }
            result.add(list);
        }
        return result;
    }

    //官方解法：动态规划
    public static List<List<Integer>> generateOffice(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();
        if (numRows == 0) {
            return triangle;
        }

        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        //从第2行开始处理。默认其他位置是0
        for (int rowNum = 1; rowNum < numRows; rowNum++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(rowNum-1);

            row.add(1);
            for (int j = 1; j < rowNum; j++) {
                row.add(prevRow.get(j-1) + prevRow.get(j));
            }
            row.add(1);
            triangle.add(row);
        }
        return triangle;
    }

}
